1. Field of the Invention
The present invention relates to the field of computer networking, specifically to the field of asynchronous transfer mode (ATM) communications. More specifically, the present invention relates to methods and apparatus for use in broadcast of cells in an ATM network.
2. Description of the Related Art
It may be worthwhile to briefly state that the present invention relates to the field of broadcast transmission of messages in an asynchronous transfer mode (ATM) network or the like. The present invention employs the concept of flooding in combination with use of hop count or similar scheme in order to effect broadcast of messages. Therefore, described below, as related art, is information on (1) ATM networks, (2) flooding of messages in networks, and (3) use of a hop count in network systems.
ATM Networks
The preferred embodiment of the present invention is implemented in an asynchronous transfer mode (ATM) network. Such networks are well-known in the art and, in fact, are described in various references. One such reference is Handel, R. and Huber, M. N., Integrated Broadband Networks, an Introduction to ATM-based Networks, published by Addison-Wesley Publishing Company, 1991 and hereinafter referred to as the Handel et al. reference. Another such reference is de Prycher, M., Asynchronous Transfer Mode solution for broadband ISDN, published by Ellis Horwood Limited, West Sussex, England, 1991.
Importantly, in ATM networks information is communicated in cells which comprise a well-defined and size-limited header area and a user information area. The switch fabric of an ATM switch is designed to act upon information in the header area in order to provide for routing of cells in the network. The switch fabric is normally implemented in hardware, for example using large-scale integrated circuits, in order to provide for high-speed switching of cells in the network. It is important to an understanding of the present invention to realize that if it was necessary to delay transmission of a cell through the switch fabric such as by accepting the cell into a memory so that a software program could examine and manipulate portions of the data in the cell, undesirable delays would result in cell transmission.
In addition, standards have been adopted for ATM networks, for example, by the International Telegraph and Telephone Consultative Committee (CCITT). The CCITT standards require a header area comprising a fixed set of fields and being of a fixed size and a payload area, also referred to as a user information area, and also of a fixed size but allowing user-defined information fields. Importantly, the CCITT standards define the header to be of a very limited size to keep at a minimum overhead associated with each cell. The standards do not allow fields to be added to the header area.
ATM Cell Format
In an ATM network, all information to be transferred is packed into fixed-size slots which are commonly referred to as cells. Of come, such fixed-size slots may be referred to with other terminology, for example, packets. In one standard ATM format (CCITT Recommendation I. 150, "B-ISDN ATM Functional Characteristics", Geneva, 1991), the format is generally shown in FIG. 1(a) and includes a 5-byte (also called octet) header field 101 and a 48-byte information field 102. The information field is defined by the standard to be available to the user and the header field is defined by the standard to carry information pertaining to ATM functionality, in particular, information for identification of the cells by means of a label. See, Handel et al., at pages 14-17.
The standardized format for the header field 101 is better shown in FIG. 1(b) and 1(c) and is described in greater detail with reference to Handel et al., at pages 84-91. The header field 101 will be discussed in greater detail below; however, it is worthwhile mentioning here that the header field 101 comprises two fields: (1) a virtual channel identifier (VCI) and (2) a virtual path identifier (VPI). The VPI field is deemed as an eight-bit field in one format (see FIG. 1 (b)) and as a twelve-bit field in another format (see FIG. 1(c)) and is defined to be used for routing of the cell. The VCI field is also used for routing in the defined format and is defined as a sixteen-bit field.
The de Prycher reference further describes the format of the ATM cell, for example at pages 55-124 and, especially at pages 106-108.
It is important to note that the defined cell header does not provide area for data supporting hop count information.
ATM Switching
Two primary tasks are accomplished by an ATM switch: (1) translation of VPI/VCI information and (2) transport of cells from the input port to the correct output port. The functions of an ATM switch are more fully described in Handel et al. at pages 113-136.
A switch is typically constructed of a plurality of switching elements which act together to transport a cell from the input of the switch to the correct output. Various types of switching elements are well-known such as matrix switching elements, central memory switching elements, bus-type switching elements, and ring-type switching elements. Each of these are discussed in greater detail in the Handel et al. reference and each carries out the above-mentioned two primary tasks.
Translation of the VPI/VCI information is important because in a standard ATM network the contents of these fields only has local meaning (i.e., the same data would be interpreted differently by each switch). Thus, the VPI/VCI information is translated by each switch and changed prior to the cell being output from the switch. Translation of the VPI/VCI field will be described in greater detail below in the Detailed Description of the Preferred Embodiment, especially with reference to FIG. 8(b) and 8(c).
Broadcast messages and Tree topologies
The present invention relates specifically to methods and apparatus for broadcast of messages. It is well-known in networking applications to provide for capability to transmit a message to all nodes on a network or all nodes on a subnetwork. Transmitting such a packet or cell to all destinations on the network (or all destinations on a subnetwork) is known as "broadcasting". Various methods have been proposed to implement broadcasting.
Of course, one simple method is to simply address individual packets to all destinations. This method is both wasteful of bandwidth and requires the impractical limitation of each sending node maintaining a complete list of addresses of all destinations.
Another method of broadcasting a message which has been commonly proposed for use in ATM networks involves use of a spanning tree. A spanning tree is a subset of the network which includes all switches but contains no loops. This may be better explained with reference to FIG. 3 which illustrates a network having three switches 311,312 and 313. A spanning tree may allow switch 1 to receive a cell on channel 301 and to output the cell on channel 303. The cell may then be received by switch 312 and be output onto channel 304. However, switch 312 will not output the message onto channel 302 because, if it did so, a loop would be formed. Importantly, this method requires superimposition of a tree topology on the network which leads to complications in set-up of the network.
A general description of broadcasting of messages may be found with reference to Tanenbaum, A. S., Computer Networks, second edition, Prentice-Hall, Inc., 1988, pp. 306-309 (hereinafter Tanenbaum). Use of a tree topology is further described in Segal, A., Barzilai, T. P., Ofek, Y. Reliable Multiuser Tree Setup with local Identifiers, IEEE Journal on Selected Areas in communications, Vol. 9, No. 9, December, 1991, pp. 1427-1439 (hereinafter the Segal reference). The Segal reference discusses use of tree topologies in ATM and ATM-like networks.
The de Prycher reference teaches that classical packet switches networks only have required point-to-point switching and that broadcast functionality has not been required. However, de Prycher teaches that in future systems broadcast functionality will be required. (See, e.g., page 130). However, discussions in the de Prycher reference suggest use of a topology-dependent scheme as the likely design to support broadcast of cells. The de Prycher reference does teach, for example, at page 107-108, that the CCITT standard does provide for a reserved value to be placed in the VCI field of the cell header to indicate the cell is to be broadcast (the value is defined to be 0000 0000 0000 0010.sub.2, e.g. 2.sub.10). However, neither the standard or the de Prycher reference is understood to teach a system utilizing the present inventions method and apparatus allowing for topology-independent broadcast of messages.
Finally, . Perlman, An algorithm for distributed computation of a spanning tree in an extended LAN, in Proc. Ninth Data Commun. Symp., Whistler Mountain, British Columbia, Sep. 10-13, 1985, pp. 44-53, (hereinafter Perlman) discloses a spanning tree algorithm for use in local area networks. In the Perlman reference, an algorithm is disclosed which allows an extended network to consist of some arbitrary topology. The algorithm is run by bridges and computes a subset of the topology that connects all LANs yet is loop-free (i.e., is a spanning tree).
Flooding and Hop-counts
Flooding of a network, a process in which every incoming packet on a network is sent out on every outgoing line, except for the line it is received on, is one known method to broadcast information on a network. Flooding is more fully described in Tanenbaum at, for example, pages 298-299. Importantly, absent some form of control, flooding may lead to infinitely looping packets in networks which have loops (e.g., non-tree structured networks).
One common form of control which is used in conjunction with flooding is use of a hop counter which is contained in each packet and which is decremented each time the packet is forwarded. When the hop counter reaches zero, the packet is discarded. It is known that, ideally, the hop counter should be initialized to the length of the path from the source to the destination. If the source does not know the length of the path, it can initialize the hop counter for a worst-case scenario.
Of course, alternatives to hop counters are available. One such alternative, utilizing sequence numbers, is described in Tanenbaum at pages 298-299. Other alternatives are, of course, within the reach of one of ordinary skill in the art. For example, instead of counting down to a predetermined value (e.g., zero) as is done with traditional hop counters, a counter may be employed which starts at a predetermined value (e.g., zero) and counts up to some maximum. Another alternative may employ use of timestamps in the messages and messages may timeout after some predetermined period of time. In general, any of these methods may be thought of as employing information in the packet to facilitate expiration of forwarding of the packet at some point in the packet's life. This type of information may be referred to herein as expiration information.
It is noted that use of timers as expiration information is described at., for example, Comer, D. E., Internetworking with TCP/IP. Vol I: Principles. Protocols. and Architecture, Second Edition, Prentice Hall, 1991 pp.91-99 (hereinafter Comer).
As has been pointed out, ATM networks employ cells having a well-defined header area. The current definition of header area does not provide an area for expiration information and the header area may not be easily expanded to include such an area both because of the need for compliance with the established standards and because expansion of the header area will cause increased overhead in cell transmission on the network. Further, it is not desirable to add expiration information within the cell's information area both because this would take valuable space in the information area and, thereby, increase overhead and because placing the expiration information in the information area may require either: (1) software translation of the information area at each switching point which would lead to a slowdown in switching of cells through the network or (2) an increase in the complexity of the switching fabric to handle additional fields of information.